◀ Prev · Parts · Full · Next ▶

• In bin packing

• The integral LP

• The fractional LP

• Solving the fractional LP

• Rounding the fractional LP

• In bin covering

• In machine scheduling

• Properties

• See also

• References

In the bin packing problem, there are n items with different sizes. The goal is to pack the items into a minimum number of bins, where each bin can contain at most B. A feasible configuration is a set of sizes with a sum of at most B.

• Example:cite-ref-2-7-0[7] suppose the item sizes are 3,3,3,3,3,4,4,4,4,4, and B=12. Then the possible configurations are: 3333; 333; 33, 334; 3, 34, 344; 4, 44, 444. If we had only three items of size 3, then we could not use the 3333 configuration.

Denote by S the set of different sizes (and their number). Denote by C the set of different configurations (and their number). For each size s in S and configuration c in C, denote:

• ns - the number of items of size s.

• as,c - the number of occurrences of size s in configuration c.

• xc - a variable denoting the number of bins with configuration c.

Then, the configuration LP of bin-packing is:

◀ Prev · Parts · Full · Next ▶